package g

// TreeNode Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

var null int = 65535

// GetTreeNode 按层获取Tree
func GetTreeNode(vals []int) *TreeNode {
	var root *TreeNode
	if len(vals) == 0 {
		return root
	}
	var curLevelNodes []*TreeNode //用于存储当前层的结点
	var fatherNodes []*TreeNode   //用于存储上一层的结点
	root = &TreeNode{Val: vals[0]}
	fatherNodes = append(fatherNodes, root)
	index := 1
	maxNum := len(fatherNodes) * 2 //用于存储每一层可以存储的最大结点个数，应该是上一层非空结点的2倍
	var saveNum int                //用于记录当前层已经存储了多少结点
	var lfFlag bool                //用于记录下一个上上层结点的左孩子还是右孩子
	for index < len(vals) {
		if vals[index] == null && saveNum < maxNum {
			saveNum++
			index++
			if index == len(vals) {
				break
			}
			lfFlag = !lfFlag
		} else {
			if saveNum < maxNum {
				tmp := &TreeNode{Val: vals[index]}
				curLevelNodes = append(curLevelNodes, tmp)
				if lfFlag {
					fatherNodes[saveNum/2].Right = tmp
					lfFlag = false
				} else {
					fatherNodes[saveNum/2].Left = tmp
					lfFlag = true
				}
				saveNum++
				index++
			} else {
				fatherNodes = fatherNodes[:0]
				for i := 0; i < len(curLevelNodes); i++ {
					fatherNodes = append(fatherNodes, curLevelNodes[i])
				}
				maxNum = len(fatherNodes) * 2
				saveNum = 0
				lfFlag = false
				curLevelNodes = curLevelNodes[:0]
			}
		}
	}
	return root
}
